package xio.leetcode.java;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * LeetCode 120 LC120_Triangle
 * <p>
 * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
 * <p>
 * 例如，给定三角形：
 * <p>
 * [
 * [2],
 * [3,4],
 * [6,5,7],
 * [4,1,8,3]
 * ]
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 * <p>
 * 思路：DP 类问题，首先写出它的状态转移方程：设三角形矩阵的末行长度为n，总共m行：
 * dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + tri[i][j]
 * 特殊情况：
 * j = 0时，dp[i][j] = dp[i-1][j] + tri[i][j]
 * j = n-1时, dp[i][j] = dp[i-1][j-1] + tri[i][j]
 * 初始状态：dp[0][0] = tri[0][0]
 * <p>
 * 遍历完后，在dp最后一行dp[m-1]中找到最小值即可；
 */
public class LC120_Triangle {
    public int minimumTotal(List<List<Integer>> triangle) {

        int result = Integer.MAX_VALUE;

        int M = triangle.size();
        if (M == 1) {
            return triangle.get(0).get(0);
        }
        int[][] dp = new int[M][triangle.get(M - 1).size()];
        // 初始状态
        dp[0][0] = triangle.get(0).get(0);
        // 开始遍历
        for (int i = 1; i < M; i++) {
            int n = triangle.get(i).size();
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j];
                } else if (j == n - 1) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
                }
                dp[i][j] += triangle.get(i).get(j);
                // 最后一行找到最小值即是结果
                if (i == M - 1) {
                    result = Math.min(result, dp[i][j]);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        LC120_Triangle tri = new LC120_Triangle();
        List<List<Integer>> data = Arrays.asList(Collections.singletonList(2), Arrays.asList(3, 4), Arrays.asList(6, 5, 7), Arrays.asList(4, 1, 8, 3));
        int result = tri.minimumTotal(data);
        System.out.println(result);
    }


}
